package com.leetcode.study;

/**
 * https://leetcode.cn/problems/search-insert-position/description/
 *
 * 搜索插入位置
 *
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。 那就是用二分查找
 *
 * 提示:
 *
 * 1 <= nums.length <= 10^4
 * -10^4 <= nums[i] <= 10^4
 * nums 为 无重复元素 的 升序 排列数组
 * -10^4 <= target <= 10^4
 */
public class L35 {

    public static void main(String[] args) {

        int[] array = {1, 3, 5, 6};
        int target = 7;
        System.out.println(searchInsert(array, target));
    }


    /**
     * 就使用二分查找的基础版就可以，查找范围就是左闭右闭。
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert(int[] nums, int target) {
        int i = 0, j = nums.length - 1;

        while (i <= j) {
            int mid = (i + j) >>> 1;

            // 目标值在比较值左边，缩小右边界，移动j指针为mid-1
            if (target < nums[mid]) {
                j = mid - 1;
            }
            // 目标值在比较值右边，缩小左边界，移动i指针为mid+1
            else if (nums[mid] < target) {
                i = mid + 1;
            }
            // 目标值==比较值
            else {
                return mid;
            }
        }

        // 如果没有找到，已经经过了i==j的阶段了，此时i走在了j前面一步了，那么这个i就是目标值应该插入的位置
        return i;
    }
}
